#include<iostream>
#include<vector>
#include<time.h>
#include<sys/timeb.h>
#include<Windows.h>
#include<math.h>
#include<algorithm>
#include<cstdlib>
#include<ctime>
//#include<RandomNumber.h> 
using namespace std;
class RandomNumber
{
	public:
		RandomNumber(){
			srand(time(0));
		}
		unsigned random(int,int);
	private:
		
};
unsigned RandomNumber::random(int begin=0,int end=1)
{
	return rand()%(end-begin+1)+begin; 
}
class Solution
{
public:
    int maxSubArray(vector<int> &nums)          //用sum记录当前的子段和，如果s变成了负数就清零，统计s的最大值
    {
        int result = INT_MIN;
        int numsSize = int(nums.size());
        int sum = 0;
        for (int i = 0; i < numsSize; i++)
        {
            sum += nums[i];
            result = max(result, sum);
            if (sum < 0)
            {
                sum = 0;
            }
        }

        return result;
    }
};
int main()
{
	DWORD start1,end1;
	start1 = GetTickCount();
	srand((unsigned)time(0));
/*	int b[]={1,2,3,1,2,3};    //情况一:输入的元素全部为正整数 
	vector<int> a(b,b + 6);*/ 
/*	int b[]={-1,-2,-3,-1,-2,-3};    //情况二:输入的元素全部为负整数
	vector<int> a(b,b + 6); */
/*	int b[]={-1,2,3,1,-2,-3};    //情况三:输入的元素包含正整数与负整数
	vector<int> a(b,b + 6); */
/*	int b[]={};    //情况四:输入的数据为空
	vector<int> a(b,b + 0); */
/*	vector<int> a;				//	情况五:输入的数据量极大
	
	for(int i = 0;i < 1000000;i++)
	{
		a.push_back(i);
	} */
	vector<int> a;				// 情况六:随机数
	RandomNumber number;
	for(int i = 0;i < 500000;i++)
	{	
		int b;
		b = number.random(-10,10);
		//cout<<b<<" ";
		a.push_back(b);
	}
	cout<<endl;
	
	Solution c;
	int d;
	d = c.maxSubArray(a);
	cout<<d<<endl;
	
	end1 = GetTickCount();
	cout<<"time(ms) "<<end1 - start1<<endl;
	
	return 0;	
} 


